An analysis of Random Restart and Iterated Improvement for Global Optimization with an application to the Traveling Salesman Problem”, Journal of optimization theory and applications

The optimization method employing iterated improvementwith random restart (I2R2) is studied. Associated with each instance of an I2R2 search is a fundamental poly-nomial, f(x) = p0x + p1x 2 +... + pdx d+1 − 1, in which the coefficient pk is the probability of starting a search k improvement steps from a local minimum. The positive root η of f can be used to calculate the convergence and speedup properties of that instance. Since the coefficients of f are naturally related to the search, it is possible to estimate them online if an a priori estimate of the size θ of the goal basin is available, for example by analysis or prior experience. In this case, the runtime statistical estimate of η converges many times faster than the estimates of the coefficients themselves. The foregoing is illustrated with an application to the traveling salesman prob-lem, TSP, using k-change as the improvement discipline. Among other things it i